package LeetCodeP;

import java.util.Arrays;

/**
 * @Author zengxianlong
 * @Date 2021/12/28 17:20
 * @Version 1.0
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 *
 * 示例 1:
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 9
 * 输出: 4
 * 解释: 9 出现在 nums 中并且下标为 4
 * 示例 2:
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 2
 * 输出: -1
 * 解释: 2 不存在 nums 中因此返回 -1
 *  
 *
 * 提示：
 *
 * 你可以假设 nums 中的所有元素是不重复的。
 * n 将在 [1, 10000]之间。
 * nums 的每个元素都将在 [-9999, 9999]之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 *
 */
public class Solution704 {
   public static void main(String[] args) {
      int[] nums = {-1,0,3,5,9,12};
      int target = 9;
      System.out.println(search2(nums,target));
   }
   //遍历方法
    static int search(int[] nums, int target) {
      for (int i=0;i<nums.length;i++){
         if (nums[i]==target){
            return i;
         }
      }
      return -1;
   }
   static int search1(int[] nums,int target){
      // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
      if (target < nums[0] || target > nums[nums.length - 1]) {
         return -1;
      }
      int left=0;
      int right=nums.length-1;//定义target在左闭右闭区间里，[left，right]
      while (left<=right){//当left==right，区间[left,right]区间还是有效，所以用<=
         int middle=left+((right-left)/2);//防止溢出，相当于(left+right)/2
         if (nums[middle]>target){
            right=middle-1;//target 在左区间，所以[left，middle-1]
         }else if (nums[middle]<target){
            left=middle+1;//target 在右区间 所以[middle+1,right]
         }else {//nums[middle]==target
            return middle;//数组中找到目标值，直接返回下标
         }
      }
      //未找到目标值
      return -1;
   }
   static int search2(int[] nums,int target){
      if (target<nums[0]||target>nums[nums.length-1]){
         return -1;
      }
      int left=0;
      int right=nums.length-1;
      while (left<=right){
         int middle=left+((right-left)/2);
         if (nums[middle]>target){
            right=middle-1;
         }else if (nums[middle]<target){
            left=middle+1;
         }else {
            return middle;
         }
      }
      return -1;
   }

}
